Skip to main content

Populating Next Right Pointers in Each Node

Question​

Given a binary tree, populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Example 1
Given the following binary tree:

     1
   /  \
  2    3
 / \  / \
4  5  6  7

The output should be:

     1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \  / \
4->5->6->7 -> NULL

Solution​

all//Populating Next Right Pointers in Each Node.py


# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return root
        queue = [root]
        while queue:
            level_size = len(queue)
            for i in range(level_size):
                curr_node = queue.pop(0)
                if i < level_size-1:
                    curr_node.next = queue[0]
                if curr_node.left:
                    queue.append(curr_node.left)
                if curr_node.right:
                    queue.append(curr_node.right)
        return root